package com.test.textGame.algorithm;

import com.test.textGame.domain.Player;
import com.test.textGame.dto.Score;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

import lombok.Getter;

@Getter
public class TopK {

	private Node[] heap;
	private int heapSize;
	// heap 中的实体映射
	private Map<Long, Node> userNodeMap;
	// heap 中的索引映射
	private Map<Long, Integer> userIndexMap;
	private NodeHeapComp comp;
	private TreeSet<Node> treeSet;

	public TopK(int k) {
		heap = new Node[k];
		heapSize = 0;
		userNodeMap = new ConcurrentHashMap<>();
		userIndexMap = new ConcurrentHashMap<>();
		comp = new NodeHeapComp();
		treeSet = new TreeSet<>(new NodeTreeSetComp());
	}

	public static class Node {
		public Player player;
		public int score;

		public Node(Player p, int s) {
			player = p;
			score = s;
		}
	}

	public static class NodeHeapComp implements Comparator<Node> {

		@Override
		public int compare(Node o1, Node o2) {
			return o1.score - o2.score;
		}

	}

	public static class NodeTreeSetComp implements Comparator<Node> {

		@Override
		public int compare(Node o1, Node o2) {
			return o2.score - o1.score;
		}
	}

	/**
	 * 核心算法，堆变化受到两个条件限制：
	 * 	1. 分数发生变化，且用户不在堆中
	 * 	2. 分数发生变化，但用户已经在堆中
	 * 	对于情况1，直接采取正常的与堆顶元素比较即可，
	 * 	对于情况2，则替换堆中原有的 node，然后重新调整堆
	 *
	 * @param player
	 * @param score
	 * @return
	 */
	public Node add(Player player, Integer score) {
		if (heap.length == 0) {
			return null;
		}
		Boolean sendMsg = false;
		Boolean replace = false;
		//找到对应节点  curNode
		Node curNode = null;
		//对应节点的用户在堆上的位置
		Integer preIndex = null;
		if (!userNodeMap.containsKey(player.getUserId())) {
			// 新用户
			curNode = new Node(player, score);
		} else {
			// 老用户,确认是否需要替换
			curNode = userNodeMap.get(player.getUserId());
			preIndex = userIndexMap.get(player.getUserId());
			if (curNode.score < score) {
				//写锁
				synchronized (TopK.class) {
					curNode.score = score;
					curNode.player = player;
					replace = true;
				}
			}
		}
		if (preIndex == null) {
			// 新用户
			if (heapSize == heap.length) {
				// 如果堆顶比 curNode 节点小， 替换堆顶
				if (comp.compare(heap[0], curNode) < 0) {
					//写锁
					synchronized (TopK.class) {
						sendMsg = true;
						Long oldPlayerId = heap[0].player.getUserId();
						Long newPlayerId = curNode.player.getUserId();
						userIndexMap.remove(oldPlayerId);
						userIndexMap.put(newPlayerId, 0);
						heap[0] = curNode;
						userNodeMap.remove(oldPlayerId);
						userNodeMap.put(newPlayerId, curNode);
						heapify(0, heapSize);
					}
				}
			} else {
				//写锁
				synchronized (TopK.class) {
					sendMsg = true;
					Long newPlayerId = curNode.player.getUserId();
					userIndexMap.put(newPlayerId, heapSize);
					heap[heapSize] = curNode;
					userNodeMap.put(newPlayerId, curNode);

					heapInsert(heapSize++);
				}

			}
		} else {
			// 老用户且需要调整堆
			if (replace) {
				//写锁
				synchronized (TopK.class) {
					sendMsg = true;
					heapify(preIndex, heapSize);
				}
			}
		}

		if (sendMsg) {
			return curNode;
		}

		return null;
	}

	public List<Score> topK() {
		List<Score> list = new ArrayList<>();
		//读锁
		synchronized (TopK.class) {
			for (Node node : heap) {
				if (node != null) {
					treeSet.add(node);
				}
			}

			for (Node node : treeSet) {
				list.add(new Score(node));
			}
			treeSet.clear();
		}

		return list;
	}



	/**
	 * 生成堆，此时堆还未成型
	 * @param index
	 */
	private void heapInsert(int index) {
		while (index != 0) {
			int parent = (index - 1) / 2;
			if (comp.compare(heap[index], heap[parent]) < 0) {
				swap(parent, index);
				index = parent;
			} else {
				break;
			}
		}
	}

	/**
	 * 调整堆
	 * @param index
	 * @param heapSize
	 */
	private void heapify(int index, int heapSize) {
		int l = index * 2 + 1;
		int r = index * 2 + 2;
		int smallest = index;
		while (l < heapSize) {
			if (comp.compare(heap[l], heap[index]) < 0) {
				smallest = l;
			}
			if (r < heapSize && comp.compare(heap[r], heap[smallest]) < 0) {
				smallest = r;
			}
			if (smallest != index) {
				swap(smallest, index);
			} else {
				break;
			}
			index = smallest;
			l = index * 2 + 1;
			r = index * 2 + 2;
		}
	}

	private void swap(int index1, int index2) {
		userIndexMap.put(heap[index1].player.getUserId(), index2);
		userIndexMap.put(heap[index2].player.getUserId(), index1);
		Node tmp = heap[index1];
		heap[index1] = heap[index2];
		heap[index2] = tmp;
	}

}